希尔排序是插入排序的一种高效的改进版,效率比插入排序要高。
希尔排序的实现思路:
- 希尔排序主要通过对数据进行分组实现快速排序;
- 根据设定的增量(gap)将数据分为gap个组(组数等于gap),再在每个分组中进行局部排序;
假如有数组有10个数据,第1个数据为黑色,增量为5。那么第二个为黑色的数据index=5,第3个数据为黑色的数据index = 10(不存在)。所以黑色的数据每组只有2个,10 / 2 = 5一共可分5组,即组数等于增量gap。
- 排序之后,减小增量,继续分组,再次进行局部排序,直到增量gap=1为止。随后只需进行微调就可完成数组的排序;
具体过程如下:
- 排序之前的,储存10个数据的原始数组为
设初始增量gap = length / 2 = 5,即数组被分为了5组,如图所示分别为:[8, 3]、[9, 5]、[1, 4]、[7, 6]、[2, 0]
随后分别在每组中对数据进行局部排序,5组的顺序如图所示,变为:[3, 8]、[5, 9]、[1, 4]、[6, 7]、[0, 2]:
- 然后缩小增量gap = 5 / 2 = 2,即数组被分为了2组,如图所示分别为:[3,1,0,9,7]、[5,6,8,4,2]:
- 随后分别在每组中对数据进行局部排序,两组的顺序如图所示,变为:[0,1,3,7,9]、[2,4,5,6,8]:
- 然后然后缩小增量gap = 2 / 1 = 1,即数组被分为了1组,如图所示为:[0,2,1,4,3,5,7,6,9,8]:
- 最后只需要对该组数据进行插入排序即可完成整个数组的排序:
动态过程:
图中d表示增量gap。
增量的选择:
- 原稿中希尔建议的初始间距为N / 2,比如对于N = 100的数组,增量序列为:50,25,12,6,3,1,可以发现不能整除时向下取整。
- Hibbard增量序列: 增量序列算法为:2^k - 1,即1,3,5,7... ...等;这种情况的最坏复杂度为 O(N3/2),平均复杂度为 O(N5/4) 但未被证明;
- Sedgewcik增量序列:
以下代码实现中采用希尔排序原稿中建议的增量即N / 2 。
//希尔排序
function shellSort aq(array){
//1.获取数组的长度
let length = array.length
//2.初始化增量
let gap = Math.floor(length / 2)
//3.第一层循环:while循环(使gap不断减小)
while(gap >= 1 ){
//4.第二层循环:以gap为增量,进行分组,对分组进行插入排序
//重点为:将index = gap作为选中的第一个数据
for(let i = gap; i < length; i++){ //i=gap 因为插入排序是从分组的第二个元素开始的
let temp = array[i]
let j = i
//5.第三层循环:直接插入排序算法的实现
while(array[j - gap] > temp && j > gap - 1){
this.array[j] = this.array[j - gap]
j -= gap
}
//6.将j位置的元素设置为temp
this.array[j] = temp
}
gap = Math.floor(gap / 2)
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
这里解释一下上述代码中的三层循环:
第一层循环: while循环,控制gap递减到1;
第二层循环: 分别取出根据增量gap分成的gap组数据:
- 将
index = gap
的数据作为选中的第一个数据,如下图所示,gap=5,则index = gap
的数据为3,index = gap - 1
的数据为8,两个数据为一组。 - 随后gap不断加1右移,直到
gap < length
,此时实现了将数组分为5组。
- 将
第三层循环: 对每一组数据进行插入排序;
分析:
希尔排序是稳定的排序算法吗:
单次直接插入排序是稳定的,它不会改变相同元素之间的相对顺序,但在多次不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,可能导致相同元素相对顺序发生变化。 因此,希尔排序
不稳定
。希尔排序的时间复杂度是多少 :
- 最佳情况:T(n) = O(n logn)。
- 最差情况:T(n) = O(n (log(n))2)。
- 平均情况:T(n) = 取决于间隙序列。
希尔排序的效率和增量有直接关系,即使使用原稿中的增量效率都高于简单排序。